Cubic Bézier approximation of a digitized curve

In this paper we present an efficient technique for piecewise cubic Bézier approximation of digitized curve. An adaptive breakpoint detection method divides a digital curve into a number of segments and each segment is approximated by a cubic Bézier curve so that the approximation error is minimized. Initial approximated Bézier control points for each of the segments are obtained by interpolation technique i.e. by the reverse recursion of De Castaljau's algorithm. Two methods, two-dimensional logarithmic search algorithm (TDLSA) and an evolutionary search algorithm (ESA), are introduced to find the best-fit Bézier control points from the approximate interpolated control points. ESA based refinement is proved to be better experimentally. Experimental results show that Bézier approximation of a digitized curve is much more accurate and uses less number of points compared to other approximation techniques.     

Metaheuristic downhill simplex method in combinatorial optimization

The concept of combinatorial objects is formalized. It allows strict definition of a combinatorial optimization problem (COP). An efficient metaheuristic method to solve COPs (H-method) is considered. It includes stochastic local search algorithms as a built-in procedure. A parallel implementation of the H-method is set forth and analyzed. The results from a numerical experiment and solution of some well-known COPs on personal computers and on the SKIT cluster supercomputer are presented. The study was supported by INTAS (Project 06-1000017-8909). __________ Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 70–79, November–December 2007.     

A novel document similarity measure based on earth mover’s distance

In this paper we propose a novel measure based on the earth mover’s distance (EMD) to evaluate document similarity by allowing many-to-many matching between subtopics. First, each document is decomposed into a set of subtopics, and then the EMD is employed to evaluate the similarity between two sets of subtopics for two documents by solving the transportation problem. The proposed measure is an improvement of the previous OM-based measure, which allows only one-to-one matching between subtopics. Experiments have been performed on the TDT3 dataset to evaluate existing similarity measures and the results show that the EMD-based measure outperforms the optimal matching (OM) based measure and all other measures. In addition to the TextTiling algorithm, the sentence clustering algorithm is adopted for document decomposition, and the experimental results show that the proposed EMD-based measure does not rely on the document decomposition algorithm and thus it is more robust than the OM-based measure.     

广义AND／OR图的自底向上的启发式搜索算法BHAO

本文首先根据三角模概念，定义了一类新的更具普遍意义的广义ＡＮＤ／ＯＲ图．根据新定义的启发式函数ｈ（ｎ，ｘ）以及广义ＡＮＤ／ＯＲ图的最佳解树之所有子树亦是最佳子解树的原理，提出了广义ＡＮＤ／ＯＲ图的自底向上的启发式搜索算法ＢＨＡＯ．文中证明了算法ＢＨＡＯ的可采纳性．本文还提出了两类新的启发式函数的单调限制概念，并据此研究了算法ＢＨＡＯ的单调限制性质，研究了两个ＢＨＡＯ算法间的比较性质．     

以数字搜索树表示的二值图象的几何变换

本文介绍以数字搜索树表示的二值图象的一种几何变换算法，文中讨论了四分区与正四边区的基本关系，输出ＤＳＴ结点成立的充分条件，给出了完整的几何变换算法并对算法的复杂性作了分析。     

基于Matlab的线性规划问题求解

线性规划是运筹学中研究较早、发展较快、应用广泛、方法成熟的一个重要分支,它是辅助人们进行科学管理的一种重要的数学方法.文章首先介绍了线性规划的基本概念及标准形式,着重讨论了线性规划问题的三种常用解法:单纯形法、直接搜索法以及遗传算法,最后在Matlab R2009a环境下进行了仿真.通过结果可以看出,用Matlab求解线性规划问题,可以避免手工的烦琐计算,大大地提高工作效率和结果的准确性.     

Intranet搜索引擎设计与实现

随着企业内部网络应用的深入,Intranet内部的信息资源越来越庞大,怎样为这些数据信息构建索引是我们面If缶的主要任务,而全文检索的产生解决了这一问题。目前越来越多的中小企业采用Linux系统作为Web平台,并且利用检索系统来管理内部繁多的文本和HTML文件。文章对www搜索引擎的全文检索及其相关技术进行了分析和讨论,实现了一个基于Linux环境的Intranet搜索引擎LISE（Linux Intranet Search Engine）。LISE利用了基于词表的索引方法,为用户提供了更加准确的信息,能满足多种中小企业用户的需求。     

DKNNS:面向延迟敏感型应用的可扩展精确分布式K近邻搜索算法研究

为了降低用户访问延迟,延迟敏感型网络应用需要选择合适的邻近服务节点响应用户访问请求.分布式K近邻搜索通过可扩展的选择距任意用户节点邻近的K个服务节点,可以有效满足网络应用延迟优化的目的.已有工作在精确度以及可扩展性等方面存在不足.针对可扩展精确的K近邻搜索问题,文中提出了分布式K近邻搜索方法DKNNS(distributed K nearest neighbor search).DKNNS将大量的服务节点组织为邻近性感知的多级环,通过最远节点搜索机制选择优化的K近邻搜索初始化节点,然后基于回退方式快速的在目标节点邻近区域发现K个近邻.基于理论分析,模拟测试以及真实环境下的部署实验发现,在不同规模的节点集合下,DKNNS算法能够确定近似最优的K个服务节点.且DKNNS的查询延迟,查询开销均显著低于Meridian算法.最后,DKNNS的返回结果相对于Meridian具有较高的稳定性.     

一个基于移动视觉搜索技术的博物馆导览系统

为了对游客的参观过程提供个性化导览服务,使游客可以通过手机拍照的方式获取展品的相关资讯.提出一个基于移动视觉搜索技术的博物馆导览系统.针对手机性能的差异性,提出一种改进的移动视觉搜索系统的框架,使得系统既能在服务器端对海量展品进行识别,又能在手机端对特定区域内展品实时识别;并基于这一框架实现了一个原型系统.与现有的导览系统相比,文中系统的交互方式更加人性化,提供的展品信息更丰富、全面,且无需在馆内安装任何辅助设备,能够更广泛地适用于博物馆导览.实验结果证明了该系统的可行性和实用性.